package dailyTopic;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-08-24 10:35
 * f[t][i] 表示通过恰好 t 次航班，从出发城市 src 到达城市 i 需要的最小花费.
 * 枚举最后一次航班的起点 j
 */
public class findCheapestPrice787 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF=10000*101+1;
        int[][] dp=new int[k+2][n];
        for (int i = 0; i < k+2; i++) {
            Arrays.fill(dp[i],INF);
        }
        dp[0][src]=0;
        for (int t = 1; t < k+2; t++) {
            for (int[] flight:flights) {
                int j=flight[0],i=flight[1],pr=flight[2];
                dp[t][i]=Math.min(dp[t][i],dp[t-1][j]+pr);
            }
        }
        int res=INF;
        for (int t = 1; t < k+2; t++) {
            res=Math.min(res,dp[t][dst]);
        }
        return res==INF?-1:res;
    }
}
